package LeetCodeHot100TopInterview;

public class Q221_MetricSquare {

    //矩阵中寻找最大正方形 返回面积
    public int maximalSquare(char[][] matrix) {

        //暴力法
        //需要对整个矩阵进行 n * m 的扫描
        //每个点都进行 n * m 的判别
        //整体时间复杂度 O(Min(M,N) ^ 2 * M * N)
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return 0;
        }
        int rLen = matrix.length; //行
        int cLen = matrix[0].length; //列

        int ans = 0;
        //全矩阵扫描
        for (int i = 0; i < rLen; i++) {
            for (int j = 0; j < cLen; j++) {
                if (matrix[i][j] == '1'){
                    ans = Math.max(ans, countMaxArea(matrix, i, j));
                }
            }
        }
        return ans;
    }

    public int countMaxArea(char[][] matrix, int row, int col){


        //先判断可能的最大正方形边长 再一次一个行列进行验证
        //有了这个 下面就不用判断越界了
        int limit = Math.min(matrix.length  - row, matrix[0].length  - col);
        int ans = 1; //能进来至少area 是个 1

        //大流程 一步一步扩展
        boolean flag;
        for (int i = 1; i < limit; i++) {
            flag = true;
            //先判断下一行下一列的交点是否 1  | 不是 break 掉
            if (matrix[row + i][col + i] == '0'){
                break;
                //答案就是上一部 ans
            }
            //从交点向上与向左判断
            for (int j = 0; j < i; j++) {
                if (matrix[row + i][col + j] == '0' || matrix[row + j][col + i] == '0'){
                    flag = false;
                    break;
                }
            }
            //上面流程走完 flag = true 代表 交点与原点之间正方形成立
            if (flag){
                //更新最大面积
                double sqrt = Math.sqrt(ans);
                ans = (int) ((sqrt + 1) * (sqrt + 1));
            }else {
                break;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        char[][] matrix = new char[][]{
                {'1','1','1','1','0'},{'1','1','1','1','0'},{'1','1','1','1','1'},{'1','1','1','1','1'},{'0','0','1','1','1'}
        };
        Q221_MetricSquare fun = new Q221_MetricSquare();
        System.out.println(fun.maximalSquare(matrix));
    }


}
